package leecode

func maximalRectangleLCR(matrix []string) int {
	if len(matrix) == 0 {
		return 0
	}
	var matrixTemp [][]byte
	for i := 0; i < len(matrix); i++ {
		temp := make([]byte, 0)
		for _, str := range matrix[i] {
			temp = append(temp, byte(str))
		}
		matrixTemp = append(matrixTemp, temp)
	}
	var result int
	heights := make([]int, len(matrixTemp[0]))
	for i := 0; i < len(matrixTemp); i++ {
		for j := 0; j < len(matrixTemp[i]); j++ {
			if matrixTemp[i][j] == '0' {
				heights[j] = 0
			} else {
				heights[j]++
			}

		}
		area := maxAreaLCR(heights)
		result = max(result, area)
	}
	return result
}

func maxAreaLCR(heights []int) (result int) {
	heights = append([]int{0}, heights...)
	heights = append(heights, 0)
	stack := make([]int, 0) // 单调栈从栈头（元素从栈头弹出）到栈底的顺序应该是从大到小的顺序。
	stack = append(stack, 0)
	for i := 1; i < len(heights); i++ {
		//栈顶元素下标
		topIndex := stack[len(stack)-1]
		for len(stack) != 0 && heights[topIndex] > heights[i] {
			//将栈顶元素弹出
			stack = stack[:len(stack)-1]
			//当前矩形的高
			h := heights[topIndex]
			w := i - stack[len(stack)-1] - 1
			result = max(result, h*w)
			if len(stack) != 0 {
				topIndex = stack[len(stack)-1]
			}
		}
		stack = append(stack, i)
	}
	return result
}
